package com.mgq.algorithm.dp;

import java.util.Arrays;

/**
 * 给定参数N,代表N个位置 N>1
 * int s表示开始位置
 * int e表示结束位置
 * int k表示必须走k步.
 * 要么往左边走,要么往右边走, 在1位置只能往右走,在N位置只能往左走
 * 计算 从s-e总共有多少种走法
 * 举例 1,2,3,4,5
 * s=2
 * e=4
 * k=4
 * 总共有4种走法
 * 2->3->4->5->4
 * 2->3->4->3->4
 * 2->3->2->3->4
 * 2->1->2->3->4
 */
public class WalkStep {

    public static void main(String[] args) {
        //System.out.println(walkStep(5, 4, 4, 2));
        System.out.println(walkStep2(5, 4, 4, 2));
    }

    public static int walkStep(int N, int E, int k, int cur) {
        return f(N, E, k, cur);
    }

    /**
     * N: 代表N个位置
     * E: 表示结束位置
     * cur: 表示开始位置
     * rest: 表示剩余的步数
     *
     * @param N
     * @param E
     * @param rest
     * @param cur
     * @return
     */
    public static int f(int N, int E, int rest, int cur) {
        //base case
        if (rest == 0) {
            return cur == E ? 1 : 0;
        }
        if (cur == 1) {
            return f(N, E, rest - 1, 2);
        } else if (cur == N) {
            return f(N, E, rest - 1, N - 1);
        } else {
            return f(N, E, rest - 1, cur - 1) + f(N, E, rest - 1, cur + 1);
        }
    }

    public static int walkStep2(int N, int E, int k, int cur) {
        //rest 是从k到0 总共长度是k+1
        //cur 是从1到N,给N+1个, int[][0]无用
        int[][] dp = new int[k + 1][N + 1];
        //因为java默认是0,f1函数将没有找到标记为0了,所以先将int[][]的默认值改成-1
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
        int result = f1(N, E, k, cur, dp);
        return result;
    }

    /**
     * 动态规划版本
     * @param N
     * @param E
     * @param rest
     * @param cur
     * @param dp
     * @return
     */
    public static int f1(int N, int E, int rest, int cur, int[][] dp) {
        //命中缓存
        if (dp[rest][cur] != -1) {
            return dp[rest][cur];
        }
        //没有命中缓存
        if (rest == 0) {
            dp[rest][cur] = cur == E ? 1 : 0;
            return dp[rest][cur];
        }
        //等于1,只能走向2
        if (cur == 1) {
            dp[rest][cur] = f1(N, E, rest - 1, 2, dp);
            return dp[rest][cur];
        }
        //等于N,只能走向N-1
        if (cur == N) {
            dp[rest][cur] = f1(N, E, rest - 1, N - 1, dp);
            return dp[rest][cur];
        }
        //其他情况是 cur-1 和cur+1
        dp[rest][cur] = f1(N, E, rest - 1, cur - 1, dp) + f1(N, E, rest - 1, cur + 1, dp);
        return dp[rest][cur];

    }
}
